package main.java.sort;

/**
 * @Author: 郑国荣
 * @Date: 2023-09-27-14:24
 * @Description:
 */
public class MergeSort {

    public void mergeSort(int[] arr){
        int n = arr.length;
        mergeSort(arr,0,n-1);
    }
    //递归使用归并排序，对arr[l...r]的范围进行排序
    private void mergeSort(int[] arr, int l, int r) {
        if (l>=r) return;
        int mid = l + (r-l)/2; // 防止整型溢出   7  中间是3  0+7/2=3 7/2=3
        mergeSort(arr,l,mid); // 递归调用
        mergeSort(arr,mid+1,r); // 递归调用,注意这里是mid+1,不是mid,否则会无限递归
        merge(arr,l,mid,r); // 合并
    }

    //将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private void merge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r-l+1];
        int i = l,j = mid+1,k = 0;
        while (i<=mid && j<=r){
            temp[k++] = arr[i]<=arr[j]?arr[i++]:arr[j++];
        }
        while (i<=mid) temp[k++] = arr[i++];
        while (j<=r) temp[k++] = arr[j++];
        for (int p = 0; p < temp.length; p++) {
            arr[l+p] = temp[p];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,3,2,5,4,7,6};
        new MergeSort().mergeSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
